package com.yun.algorithm.recursion_multi;

import org.springframework.util.StopWatch;

import java.util.LinkedList;

/**
 * 多路递归
 * 汉诺塔
 */
public class HanoiTower {
    static LinkedList<Integer> a = new LinkedList<>();
    static LinkedList<Integer> b = new LinkedList<>();
    static LinkedList<Integer> c = new LinkedList<>();

    static void init(int n) {
        for (int i = 1; i <= n; i++) {
            a.addFirst(i);
        }
    }

    /**
     * @param n-圆盘个数
     * @param a-初始柱子
     * @param b-借用柱子
     * @param c-目标柱子
     *         T(n)=2T(n-1)+c,o(2^n)
     */
    static void move(int n, LinkedList<Integer> a,
                     LinkedList<Integer> b,
                     LinkedList<Integer> c) {
        if (n == 0) {
            return;
        }
        move(n - 1, a, c, b);
        c.addLast(a.removeLast());
        print();
        move(n - 1, b, a, c);
    }

    public static void main(String[] args) {
        StopWatch sw=new StopWatch();
        int n =1;
        init(n);
        print();
        sw.start("n="+n);
        move(n,a,b,c);
        sw.stop();
        System.out.println(sw.prettyPrint());
    }

    private static void print() {
        System.out.println("------");
        System.out.println(a);
        System.out.println(b);
        System.out.println(c);
    }
}
